#include "TaskAssigner.h"
#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>

using namespace std;

// 构造函数，初始化员工数和任务数
TaskAssigner::TaskAssigner(int employees, int tasks)
    : numEmployees(employees), numTasks(tasks), 
      dissatisfaction(employees, vector<int>(tasks)), 
      taskAssignments(tasks), employeeAssignment(employees, -1), 
      minTotalDissatisfaction(INT_MAX) {}

// 从文件加载不满意度矩阵
void TaskAssigner::loadDissatisfactionMatrix(const string& filename)
{
    ifstream inputDissatisfaction(filename);
    if (!inputDissatisfaction.is_open())
    {
        cerr << "Error opening file!" << endl;
        return;
    }

    inputDissatisfaction >> numEmployees >> numTasks;   //读取员工数和任务数量

    for (int i = 0; i < numEmployees; i++)
    {
        for (int j = 0; j < numTasks; j++)
        {
            inputDissatisfaction >> dissatisfaction[i][j]; // 从文件中读取不满意度
        }
    }
    inputDissatisfaction.close();
}

// 计算当前任务分配的不满意度
double TaskAssigner::calculateTotalDissatisfaction(int taskIndex)
{
    double totalDissatisfaction = 0;
    for (int j = 0; j < taskIndex; ++j)
    {
        double taskDissatisfaction = 0;
        for (int employee : taskAssignments[j])
        {
            taskDissatisfaction += dissatisfaction[employee][j];
        }
        totalDissatisfaction += taskDissatisfaction;
    }
    return totalDissatisfaction;
}

// 回溯法实现任务分配
void TaskAssigner::backtrack(int taskIndex)
{
    double currentDissatisfaction = calculateTotalDissatisfaction(taskIndex);
    if(currentDissatisfaction >= minTotalDissatisfaction)
    {   //剪枝优化，如果目前的不满意度已经超过了最小的，则直接跳过
        return;
    }

    if (taskIndex == numTasks)
    {
        // 所有任务已经分配完成，计算当前分配方式的不满意度
        double currentDissatisfaction = calculateTotalDissatisfaction(taskIndex);
        if (currentDissatisfaction < minTotalDissatisfaction)
        {
            minTotalDissatisfaction = currentDissatisfaction;
            bestAssignments = taskAssignments;
        }
        return;
    }

    // 当前任务的员工选择范围
    vector<pair<double, int>> dissatisfactionForEmployees;
    for (int i = 0; i < numEmployees; ++i)
    {
        if (employeeAssignment[i] == -1)
        { // 该员工还未被分配任务
            dissatisfactionForEmployees.push_back({dissatisfaction[i][taskIndex], i});
        }
    }

    // 贪心策略，按照不满意度从小到大排序，选择最小不满意度的员工
    sort(dissatisfactionForEmployees.begin(), dissatisfactionForEmployees.end());

    // 尝试为当前任务分配最小不满意度的前两个员工
    for (int i = 0; i < dissatisfactionForEmployees.size(); ++i)
    {
        for (int j = i + 1; j < dissatisfactionForEmployees.size(); ++j)
        {
            int employee1 = dissatisfactionForEmployees[i].second;
            int employee2 = dissatisfactionForEmployees[j].second;

            // 为当前任务分配这两个员工
            taskAssignments[taskIndex] = {employee1, employee2};
            employeeAssignment[employee1] = taskIndex;
            employeeAssignment[employee2] = taskIndex;

            // 递归调用回溯，分配下一个任务
            backtrack(taskIndex + 1);

            // 恢复状态
            employeeAssignment[employee1] = -1;
            employeeAssignment[employee2] = -1;
        }
    }
}

// 执行任务分配，从第0个任务开始
void TaskAssigner::assignTasks()
{
    backtrack(0);
}

// 输出最终结果
void TaskAssigner::displayResults()
{
    cout << "Minimum Total Dissatisfaction: " << minTotalDissatisfaction << endl;
    for (int j = 0; j < numTasks; ++j)
    {
        cout << "Task " << j + 1 << " is assigned to employees: ";
        for (int employee : bestAssignments[j])
        {
            cout << employee + 1 << " ";  // 输出员工编号
        }
        cout << endl;
    }
}
